import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: lenovo
 * Date: 2022-09-02
 * Time: 8:32
 */
public class Sort {
    /**
     * 插入排序
     * 时间复杂度:最坏:逆序 O(n^2) 最好:顺序 O(n),越有序越快,有序时,j的for循环不进入if语句,而是直接进入break,因此j并没有回退
     * 结论：对于直接插入排序来说，数据越有序越快。
     * 场景：当数据基本上是有序的时候，使用直接插入排序
     * 空间复杂度:O(1)
     * 稳定性:稳定
     *
     */
    public static void insertSort(int[] array){
        for (int i = 1; i <array.length; i++) {
            int tmp = array[i];
            int j = i-1;
            for ( ;j >=0 ; j--) {
                if(array[j]>tmp){//如果加上了等号就是一个不稳定的排序
                    array[j+1]=array[j];
                }else {
                    break;
                }
            }
            array[j+1]=tmp;

        }

    }
    /**
     * 希尔排序
     * 时间复杂度:O(n^1.35~n^1.5)
     * 空间复杂度:O(1)
     * 稳定性:不稳定
     *
     */
    public static void shellSort(int[] array){
        int gap = array.length;
        while (gap >1){
            shell(array,gap);
            gap/=2;
        }
        shell(array,1);
    }
    private static void shell(int[] array,int gap){
        //这里i必须是++
        for (int i = gap; i <array.length ; i++) {
            int tmp = array[i];
            int j = i-gap;
            for ( ;j >=0 ; j-=gap) {
                if (array[j]>tmp){
                    array[j+gap]=array[j];
                }else {
                    break;
                }
            }
            array[j+gap]=tmp;
        }
    }
    /**
     *选择排序
     *时间复杂度:O(n^2) 对数据不敏感
     * 空间复杂度:1
     * 稳定性:不稳定
     */
    public static void selectSort(int[] array){
        for (int i = 0; i < array.length; i++) {
            //最小值的下标
            int minIndex = i;
            int j = i+1;
            for ( ;j <array.length ; j++) {
                if(array[j] < array[minIndex]){//不管是否加=号,都不稳定,加了更不稳定
                    minIndex = j;
                }

            }
            swap(array,minIndex,i);
        }
    }
    private static void swap(int[] array,int i,int j){
        int tmp = array[i];
        array[i] =array[j];
        array[j] = tmp;
    }
    /**
     * 选择排序:maxIndex,minIndex
     * 时间复杂度:O(n^2)
     */
    public static void selectSort1(int[] array){
        int left = 0;
        int right = array.length-1;

        while (left<right){
            int minIndex = left;
            int maxIndex = left;
            for (int i = left+1; i <right ; i++) {
                if(array[i]<array[minIndex]){
                    minIndex=i;
                }
                if(array[i]>array[maxIndex]){
                    maxIndex=i;
                }
            }

            swap(array,minIndex,left);
            //修正maxIndex==left的情况
            if(left == maxIndex){
                maxIndex=minIndex;
            }
            swap(array,maxIndex,right);
            left++;
            right--;
        }

    }
    /**
     * 堆排序:1.创建大根堆 2.调整堆顶到end
     * 时间复杂度:创建大根堆n*调整的高度log2n n*log2n
     */
    public static void heapSort(int[] array){
        createBigheap(array);
        int end = array.length-1;
        while (end>=0){
           swap(array,0,end);
           shiftdown(array,0,end);
           end--;
        }

    }
   public static void createBigheap(int[] array){
        for (int parent = (array.length-2)/2; parent >=0 ; parent--) {
            shiftdown(array,parent,array.length);
        }


    }
    private static void shiftdown(int[] array,int parent,int len){
        //左孩子节点
        int child = 2*parent+1;
        while (child < len){
            if(child+1<len &&array[child]<array[child+1]){
                child++;
            }
            if(array[child]>array[parent]){
                swap(array,child,parent);
            }
            parent=child;
            child=2*parent+1;
        }

    }
    /**
     * 冒泡排序
     * 时间复杂度:O(n^2) 优化后:O(n)
     * 空间复杂度:O(1)
     * 稳定性:稳定的
     * 插入排序也是稳定的
     *
     */
    public static void bubbleSort(int[] array){
        for (int i = 0; i < array.length-1; i++) {
            //优化,默认有序
            boolean flag = true;
            for (int j = 0; j < array.length-1-i; j++) {
                if(array[j]>array[j+1]){//加了=不稳定
                    swap(array,j,j+1);
                    flag = false;
                }
            }
            if(flag){
                return;
            }
            
        }
    }
    /**
     * 快速排序:
     * 时间复杂度:理想:每次递归左右对称n*log2n   最坏:有序 单边递归 O(n^2)
     */
    public static void quickSort(int[] array){
        quick(array,0,array.length-1);
    }

    private static void quick(int[] array,int left, int right){
        //这里代表 只要一个节点了 大于号：有可能没有子树  有序  逆序
        if(left >= right){
            return;
        }
//        //三数取中：解决递归深度问题 基本上 有了三数取中  你的待排序序列 基本上每次都是二分N*logn
//        int mid = midNum(array,left,right);
//        swap(array,left,mid);

//        ////小区间使用直接插入排序： 主要 优化了递归的深度
//        if(right - left + 1 < 7){
//            insertSort2(array,left,right);
//        }
        //int pivot = pivot(array,left,right);
        int pivot = digQuick(array,left,right);
        //int pivot = pivot(array,left,right);
        //左子树
        quick(array,left,pivot-1);
        //右子树
        quick(array,pivot+1,right);
        return;
    }

    /**
     * 这里的插入排序,区间不是数组的长度,而是快排的左右区间
     * 原先的0 改成start(left) 原先的array.len 改成end(right)
     */
    public static void insertSort2(int[] array,int start,int end){
        for (int i = start+1; i <end; i++) {
            int tmp = array[i];
            int j = i-1;
            for ( ;j >=start ; j--) {
                if(array[j]>tmp){//如果加上了等号就是一个不稳定的排序
                    array[j+1]=array[j];
                }else {
                    break;
                }
            }
            array[j+1]=tmp;

        }

    }
    /**
     * 三数取中法
     * @param array
     * @param left
     * @param right
     * @return
     */

    private static int midNum(int[] array,int left, int right){
        int mid = (left+right)/2;
        if(array[left]<array[right]){
            if(array[mid] < array[left]){
                return left;
            }else if (array[mid] > array[right]){
                return right;
            }else {
                return mid;
            }
        }else {//array[left]>array[right]
            if(array[mid] < array[right]){
                return right;
            }else if(array[mid] > array[left]){
                return left;
            }else {
                return mid;
            }

        }
    }
    /**
     * hoare法
     * @param array
     * @param start
     * @param end
     * @return
     */
    private  static int pivot(int[] array,int start, int end){
        //基准值下标
        int key = start;
        while (start< end){
            //先动右边
            while (start<end && array[end] >= array[key]){
                //往前找比key小的值
                end--;
            }
            //在动左边
            while (start<end && array[start] <= array[key]){
                //往前找比key小的值
                start++;
            }
            //代码走到这里start和end里已经有了满足条件的值
            swap(array,start,end);
        }
        //代码走到这里,start==end,交换key处的值和start处的值
        swap(array,start,key);
        return start;
    }

    /**
     * 挖坑法
     * @param array
     * @param start
     * @param end
     * @return
     */
    private static int digQuick(int[] array,int start,int end){
        int key = array[start];
        while (start < end ){
            while (start<end && array[end] >= key){
                end--;
            }
            //代码走到这里,array[end]<key
            array[start] = array[end];
            while (start<end && array[start] <= key){
                start++;
            }
            //代码走到这里,array[start]>key
            array[end] = array[start];
        }
        //代码走到这里,start == end
        array[start] = key;
        return start;
    }
    /**
     * 前后指针法
     */
    private static int point(int[] array,int strat,int end){
        int prev = strat;
        int cur = prev+1;
        while (cur <= end){
            if(array[cur] < array[end] && array[++prev] != array[cur]){
                swap(array,prev,cur);
            }
            cur++;
        }
        swap(array,strat,prev);
        return prev;

    }

    /**
     * 快速排序的非递归实现,用栈来实现
     */
    public  static void quickStack(int[] array){
        //创建一个栈
        Stack<Integer> stack = new Stack();
        int left = 0;
        int right = array.length-1;
        /**
         * 这里需要先执行一次快排找到key的位置
         */
        //三数取中
        int midIndex = midNum(array,left,right);
        swap(array,left,midIndex);
        int pivot = digQuick(array,left,right);

        //将key的左区间压入栈里
        if(pivot > left+1){//左区间只有一个元素时,不用在入栈了
            stack.push(left);
            stack.push(pivot-1);
        }
        if(pivot<right-1){//右区间只有一个元素时,不用在入栈了
            //将key的右区间压入栈里
            stack.push(right);
            stack.push(pivot+1);
        }
        //栈里面的元素如果没有为空,则排序还没有排完
        while(!stack.empty()){
            //注意栈是先进后出
            right = stack.pop();
            left = stack.pop();
            midIndex = midNum(array,left,right);
            swap(array,left,midIndex);
            pivot = digQuick(array,left,right);

            if(pivot > left+1){
                stack.push(left);
                stack.push(pivot-1);
            }
            if(pivot<right-1){
                //将key的右区间压入栈里
                stack.push(right);
                stack.push(pivot+1);
            }
        }

    }
}
